/****************************************************************************
'binarytree.c' - implements functions that perform operations or manipulations
            on Binary Trees (see header file for type definition)
          - Programmer: Vincent Paul Fiestada
*****************************************************************************/

#include "binarytree.h" // Unnecessary since the header file includes this, but retain for readability
#include "stack.h"
#include "queue.h"

// <summary>
// CreateBinaryTree() - returns a pointer to a newly allocated binary tree
// </summary>
BinaryTree * CreateBinaryTree()
{
 	BinaryTree * tree = malloc(sizeof(BinaryTree));
 	tree->Root = NULL;
 	return tree;
}

// <summary>
// PrintBinaryTree(...) - goes through the tree in preorder, printing the Data in each node visited
//                      - for formatting, takes in 'spaces', the number of spaces in front of the root node
// </summary>
void PrintBinaryTree(BinaryTreeNode * root, int spaces)
{
	BinaryTreeNode * left;
	BinaryTreeNode * right;
	int i = 0;

	if(root != NULL)
	{
		// Retain pointers to left and right branches
		left = root->LeftBranch;
		right = root->RightBranch;
		// Print current subtree root
		printf("\n");
		for (i = 0; i < spaces*4; i++)
		{
			if (i%4 == 0) printf("--|");
			else printf("-");
		}
		printf("[ %c ]", root->Data);
		PrintBinaryTree(left, spaces + 1); // Print left branch
		PrintBinaryTree(right, spaces + 1); // Print right branch
	}
	return;
}

// <summary>
// AnnihilateBinaryTree(...) - uproots a binary tree and then destroys the 'tree' itself
// </summary>
void AnnihilateBinaryTree(BinaryTree * tree)
{
	BinaryTreeNode * root = tree->Root;
	UprootBinaryTree(root); // delete all nodes
	free(tree); // delete the tree itself
	return;
}

// <summary>
// UprootBinaryTree(...) - frees up / deletes the nodes of a binary tree in Preorder
// </summary>
void UprootBinaryTree(BinaryTreeNode * root)
{
	BinaryTreeNode * left;
	BinaryTreeNode * right;

	if(root != NULL)
	{
		// Retain pointers to left and right branches
		left = root->LeftBranch;
		right = root->RightBranch;
		// Delete current subtree root
		free(root);
		UprootBinaryTree(left); // Delete left branch
		UprootBinaryTree(right); // Delete right branch
	}
	return;
}

// <summary>
// PreInordertoBinTree(...) - takes two strings: a preorder traversal and an inorder traversal of a binary tree
//                            and reconstructs the binary tree
//							- returns a pointer to the tree (which must be created beforehand and
//						      is passed as an argument)
//                          - returns NULL if an error is encountered (tree could not be fully reconstructed)
//							- assumes that traversal strings are valid
// </summary>
BinaryTree * PreInordertoBinTree(BinaryTree * tree, char * preorder, char * inorder)
{
	int length = strlen(preorder); // Get length of traversals
	Stack * nodeStack = CreateNewStack();
	int found = 0; // index returned by strchr(...)
	char * tempc = 0;
	int i = 0; // iterator

	for (i = 0; i < length; i++)
	{
		// Create new node
		BinaryTreeNode * node = malloc(sizeof(BinaryTreeNode));
		node->Data = preorder[i];
		node->LeftBranch = NULL;
		node->RightBranch = NULL;
		node->Tag = 0;

		// Insert into tree:
		//   If tree is empty, node becomes the root
		if (tree->Root == NULL)
		{
			tree->Root = node;
			// Find index in inorder string
			tempc = strchr(inorder, node->Data);
			found = (tempc == NULL) ? -1 : (int)(tempc - inorder);
			if (found == -1)
			{
				fprintf(stderr,"\nInvalid Input\nPreorder and Inorder Mismatch. '%c' not found in Inorder String.", node->Data);
				return NULL;
			}
			// add to stack: left branch is from 0 to found - 1; right branch from found + 1 to end
			PushToStack(nodeStack, node, 0, found - 1, found + 1, length - 1);
		}
		// If tree is not empty, check left and right branches of the node at the top of the stack
		else
		{
			while(1)
			{
				// end loop if stack is empty; note that when this else branch is first run, there is 1 node inside the stack
				//   because of the previous if branch
				if (nodeStack->Top == NULL) break;
				// Find index in inorder string
				tempc = strchr(inorder, node->Data);
				found = (tempc == NULL) ? -1 : (int)(tempc - inorder);

                if (found == -1)
                {
                    // NOT FOUND! Invalid Input
                    fprintf(stderr,"\nInvalid Input\nPreorder and Inorder Mismatch. '%c' not found in Inorder String.", node->Data);
                    return NULL;
                }
				else if (found < nodeStack->Top->LF || found > nodeStack->Top->RL)
				{
					(void)PopFromStack(nodeStack);
					continue; // character is not in left or right branches
							  // pop from stack and check again using new top node
				}
				// is it within the left branch?
				else if (found <= nodeStack->Top->LL && found >= nodeStack->Top->LF)
				{
					// If within left branch, make left child of the node at the top of the stack
					nodeStack->Top->Data->LeftBranch = node;
					// add to stack
					// left branch is from last left branch's beginning to found - 1
					// right branch is from found + 1 to last left branch's end
					PushToStack(nodeStack, node, nodeStack->Top->LF, found - 1, found + 1,  nodeStack->Top->LL);
					break;
				}
				else if (found <= nodeStack->Top->RL && found >= nodeStack->Top->RF)
				{
					// If within right branch, make right child of the node at the top of the stack
					nodeStack->Top->Data->RightBranch = node;
					// add to stack
					// left branch is from last right branch's beginning to found - 1
					// right branch is from found + 1 to last right branch's end
					PushToStack(nodeStack, node, nodeStack->Top->RF, found - 1, found + 1,  nodeStack->Top->RL);
					break;
				}
				else // Handle errors
				{
					// Clean up stack
					AnnihilateStack(nodeStack);
					return NULL;
				}
			}
		}
	}

	// Clean up stack
	AnnihilateStack(nodeStack);
	return tree;
}

/********************************************************
 what follows are "component functions"
 of LinkInversionTraversal(..); they abstract the functionality
 required by the aforementioned function
 these functions were separated in order
 to shorten the code of LinkInversionTraversal(..)
 and to avoid spaghetti code and using goto

 IMPORTANT:
 These functions were never meant to be used by any other function
 except for LinkInversionTraversal
 LinkInversionTraversal(...) will not work without them
*********************************************************/

// Concatenates data in current node into the destination string
void LIT_Visit(BinaryTreeNode * beta, char * dest)
{
    char temp[2] = {beta->Data,'\0'};
    strcat(dest, temp);
}

// Descends Left into the tree; returns true if we must continue descending in the same direction
//  otherwise, returns false
bool LIT_DescendLeft(BinaryTreeNode ** alpha, BinaryTreeNode ** beta, BinaryTreeNode ** sigma)
{
    *sigma = (*beta)->LeftBranch;
    if (*sigma)
    {
        (*beta)->LeftBranch = *alpha;
        *alpha = *beta;
        *beta = *sigma;
        return true; // A left child exists, return true to indicate a descent
    }
    return false;
}

bool LIT_DescendRight(BinaryTreeNode ** alpha, BinaryTreeNode ** beta, BinaryTreeNode ** sigma)
{
    *sigma = (*beta)->RightBranch;
    if (*sigma)
    {
        (*beta)->RightBranch = *alpha;
        (*beta)->Tag = 1;
        *alpha = *beta;
        *beta = *sigma;
        return true;
    }
    return false;
}

void LIT_AscendLeft(BinaryTreeNode ** alpha, BinaryTreeNode ** beta, BinaryTreeNode ** sigma)
{
    // Ascend using left branch pointer
    *sigma = (*alpha)->LeftBranch;
    (*alpha)->LeftBranch = *beta; // Restore pointer to child
    *beta = *alpha; // Current node is now the parent
    *alpha = *sigma; // Parent is now the grandfather
    return;
}

void LIT_AscendRight(BinaryTreeNode ** alpha, BinaryTreeNode ** beta, BinaryTreeNode ** sigma)
{
    // Same as LIT_AscendLeft, but uses right branch pointer
    *sigma = (*alpha)->RightBranch;
    (*alpha)->RightBranch = *beta;
    (*alpha)->Tag = 0; // reset tag
    *beta = *alpha;
    *alpha = *sigma;
    return;
}

/********************************************************
 The following is the definition of LinkInversionTraversal(...)
********************************************************/

//<summary>
// LinkInversionTraversal(...) - returns a string with the traversal of a tree
//                             - uses link inversion
//                             - can produce POSTORDER, LEVEL ORDER, CONVERSE PREORDER,
//                               CONVERSE INORDER, and CONVERSE POSTORDER
//                             - returns a NULL if there is an error and copies the error
//                               message into the string
//</summary>
char * LinkInversionTraversal(BinaryTree * tree, char * dest, int mode)
{
    BinaryTreeNode * alpha;
    BinaryTreeNode * beta;
    BinaryTreeNode * sigma;

    if (tree->Root == NULL) return dest; // Tree is empty, so traversal is also empty
    alpha = NULL;
    beta = tree->Root;

    if (mode == 1) // PREORDER
    {
        while(1)
        {
            // Visit Current Node
            LIT_Visit(beta, dest);
            // Descend into left branch
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue; // Left branch exists, visit it
            // Descend into right branch
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue; // Right branch exists, visit it
            // Ascend from darkness; Check out parents
            while(1)
            {
                if (alpha == NULL) return dest; // Does parent exist? If not, we're done
                else if (alpha->Tag == 0)
                {
                    // Ascend left
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    // Descend into right branch
                    if (LIT_DescendRight(&alpha, &beta, &sigma)) break;
                }
                else
                {
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    continue;
                }
            }
        }
    }
    // The following else-if branches are the same as the first one (PREORDER)
    //    but with rearranged order
    else if (mode == 2) // INORDER
    {
        while(1)
        {
            // Descend in INORDER
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue;
            LIT_Visit(beta, dest);
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue;
            // Ascend
            while(1)
            {
                if (alpha == NULL) return dest; // Does parent exist? If not, we're done
                else if (alpha->Tag == 0)
                {
                    // Ascend left
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    LIT_Visit(beta, dest);
                    // Descend into right branch
                    if (LIT_DescendRight(&alpha, &beta, &sigma)) break;
                }
                else
                {
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    continue;
                }
            }
        }
    }
    else if (mode == 3) // POSTORDER
    {
        while(1)
        {
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue;
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue;
            LIT_Visit(beta, dest);
            while(1)
            {
                if (alpha == NULL) return dest;
                else if (alpha->Tag == 0)
                {
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    if (LIT_DescendRight(&alpha, &beta, &sigma)) break;
                }
                else
                {
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    continue;
                }
            }
        }
    }
    else if (mode == 5) // CONVERSE PREORDER
    {
        while(1)
        {
            LIT_Visit(beta, dest);
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue;
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue;
            while(1)
            {
                if (alpha == NULL) return dest;
                else if (alpha->Tag == 0)
                {
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    continue;
                }
                else
                {
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    if (LIT_DescendLeft(&alpha, &beta, &sigma)) break;
                }
            }
        }
    }
    else if (mode == 6) // CONVERSE INORDER
    {
        while(1)
        {
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue;
            LIT_Visit(beta, dest);
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue;
            while(1)
            {
                if (alpha == NULL) return dest;
                else if (alpha->Tag == 0)
                {
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    continue;
                }
                else
                {
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    LIT_Visit(beta, dest);
                    if (LIT_DescendLeft(&alpha, &beta, &sigma)) break;
                }
            }
        }
    }
    else if (mode == 7) // CONVERSE POSTORDER
    {
        while(1)
        {
            if (LIT_DescendRight(&alpha, &beta, &sigma)) continue;
            if (LIT_DescendLeft(&alpha, &beta, &sigma)) continue;
            LIT_Visit(beta, dest);
            while(1)
            {
                if (alpha == NULL) return dest;
                else if (alpha->Tag == 0)
                {
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    LIT_AscendLeft(&alpha, &beta, &sigma);
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    continue;
                }
                else
                {
                    if (strchr(dest, beta->Data)==NULL) LIT_Visit(beta, dest);
                    LIT_AscendRight(&alpha, &beta, &sigma);
                    if (LIT_DescendLeft(&alpha, &beta, &sigma)) break;
                }
            }
        }
    }
}

//<summary>
//</summary>
char * LevelOrderTraversal(BinaryTreeNode * root, char * dest)
{
    if (root == NULL) return dest; // if tree is empty, return
    Queue * nodeQ = CreateNewQueue();

    // Enqueue the root node
    Enqueue(nodeQ, root);
    while(nodeQ->Head != NULL) // traverse while queue is not empty
    {
        root = Dequeue(nodeQ);
        if (root->LeftBranch) // Enqueue Left Branch if it exists
        {
            Enqueue(nodeQ, root->LeftBranch);
        }
        if (root->RightBranch) // Enqueue Right Branch if it exists
        {
            Enqueue(nodeQ, root->RightBranch);
        }
        LIT_Visit(root, dest); // visit current node
    }
    // Clean up
    AnnihilateQueue(nodeQ);
    return dest;
}